#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


//硬币选择，有1,3,5币值的硬币，如何凑够11，使所需要的硬币数量最小
//分治实现
//输出币值，输出最小硬币数量
int func(int n)
{
    if(n == 1 || n == 3 || n == 5)
    {
        return 1;
    }
    if(n == 2 || n == 4)
    {
        return 2;
    } 
    else 
    {
        int n1 =  1 + func(n - 1);
        int n2 = 1 + func(n -3);
        int n3 = 1 + func(n -5);
        return min({n1,n2,n3});
    }
}
//动态规划,递归实现
//核心就是将每个已经走过的子问题的解，存放在dp数组当中，下次再遇到这个子问题直接去dp数组中拿结果。
int func(int dp[],int n)
{
    if(dp[n] > 0)
    {
        return dp[n];
    }
    if(n == 1 || n == 3 || n == 5)
    {
        dp[n] = 1;
        return dp[n];
    }
    if(n == 2 || n == 4)
    {
        dp[n] = 2;
        return dp[n];
    } 
    else 
    {
        int n1 =  1 + func(n - 1);
        int n2 = 1 + func(n -3);
        int n3 = 1 + func(n -5);
        dp[n] = min({n1,n2,n3});
        return dp[n];
    }
}
//动态规划,非递归实现
int n_func(int n)
{
    vector<int> dp(n + 1,0);
    dp[0] = 0;
    dp[1] = 1 + dp[1 -1];
    dp[2] = 1 + dp[2 - 1];
    //dp[3] = 1 + dp[3 - 1];选择三个一分硬币
    // 或者 dp[3] = 1 + dp[0]; 选择一个三分硬币
    dp[3] = 1;
    dp[4] = 1 + dp[ 4 - 1];
    dp[5] = 1;
    for(int i = 6;i <= n;i++)
    {
        int n1 = 1 + dp[i -1];
        int n2 = 1 + dp[i -3];
        int n3 = 1 + dp[i - 5];
        dp[i] = min({n1,n2,n3});
    }
    return dp[n];
}
int main()
{
    const int n = 11;
    
    int coins = n_func(n);
    cout << coins << endl;
}